<!doctype html>
<html lang="en">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta name="description" content="coinfaces">

        <title>从指数级增长到对数级增长</title>

    <link rel="stylesheet" href="../../theme/css/style.css">
    <link rel="stylesheet" href="../../theme/css/pygments.css">



</head>

<body>
    <div class="content">
<h1>从指数级增长到对数级增长</h1>    <p>
        under
    </p>
    <p>
        in <a href="../../categories/algorithm/">algorithm</a>
    </p>
    <p>Published: 2016-11-24</p>


    <p>Fibonacci数是递归的经典例子，最简单的算法可以根据Fibonacci数的定义直接写出来：</p>
<div class="highlight"><pre><span></span><span class="p">(</span><span class="k">define </span><span class="p">(</span><span class="nf">fib</span> <span class="nv">n</span><span class="p">)</span>
  <span class="p">(</span><span class="k">cond </span><span class="p">((</span><span class="nb">&lt; </span><span class="nv">n</span> <span class="mi">2</span><span class="p">)</span> <span class="nv">n</span><span class="p">)</span>
        <span class="p">(</span><span class="k">else </span><span class="p">(</span><span class="nb">+ </span><span class="p">(</span><span class="nf">fib</span> <span class="p">(</span><span class="nb">- </span><span class="nv">n</span> <span class="mi">1</span><span class="p">))</span> <span class="p">(</span><span class="nf">fib</span> <span class="p">(</span><span class="nb">- </span><span class="nv">n</span> <span class="mi">2</span><span class="p">))))))</span>
</pre></div>
<p>这种算法的时间复杂度是指数级，因为它实际上是遍历了一个二叉树，树的结点介于<span class="math">\(fib(n+1)\)</span>和<span class="math">\(2^{n+1}\)</span>之间，其中前者以很快的速度接近<span class="math">\((\frac{\sqrt{5}+1}{2})^{n+1} / \sqrt{5}\)</span>。</p>
<p>这种算法包含了非常多的重复计算，例如<span class="math">\(fib(n-2)\)</span>这棵树要被计算2次，如果人工计算Fibonacci数，大部分人会采用迭代算法：</p>
<div class="highlight"><pre><span></span><span class="p">(</span><span class="k">define </span><span class="p">(</span><span class="nf">fib</span> <span class="nv">n</span><span class="p">)</span>
  <span class="p">(</span><span class="k">define </span><span class="p">(</span><span class="nf">fib-iter</span> <span class="nv">k</span> <span class="nv">a</span> <span class="nv">b</span><span class="p">)</span>
    <span class="p">(</span><span class="k">cond </span><span class="p">((</span><span class="nb">= </span><span class="nv">k</span> <span class="nv">n</span><span class="p">)</span> <span class="nv">b</span><span class="p">)</span>
          <span class="p">(</span><span class="k">else </span><span class="p">(</span><span class="nf">fib-iter</span> <span class="p">(</span><span class="nb">+ </span><span class="nv">k</span> <span class="mi">1</span><span class="p">)</span> <span class="p">(</span><span class="nb">+ </span><span class="nv">a</span> <span class="nv">b</span><span class="p">)</span> <span class="nv">a</span><span class="p">))))</span>
  <span class="p">(</span><span class="nf">fib-iter</span> <span class="mi">0</span> <span class="mi">1</span> <span class="mi">0</span><span class="p">))</span>
</pre></div>
<p>这种算法消耗的时间正比于参数<tt class="docutils literal">n</tt>。</p>
<p>然而还有更快的算法，在迭代算法中，每一次迭代都相当于一次线性变换：</p>
<div class="math">
\begin{equation*}
\begin{bmatrix} fib(n+1)\\ f(n) \end{bmatrix} =
\begin{bmatrix} 1&amp; 1\\ 1&amp; 0 \end{bmatrix}
\begin{bmatrix} fib(n)\\ f(n-1) \end{bmatrix}
\end{equation*}
</div>
<p>令<span class="math">\(A = \begin{bmatrix}1&amp; 1\\1&amp; 0\end{bmatrix}\)</span>，则：</p>
<div class="math">
\begin{equation*}
\begin{bmatrix} fib(n)\\ f(n-1) \end{bmatrix} =
A^{n-1} \begin{bmatrix} fib(1)\\ f(0) \end{bmatrix}
\end{equation*}
</div>
<p>其实就是指数的计算，可以用对数时间复杂度的算法完成：</p>
<div class="highlight"><pre><span></span><span class="p">(</span><span class="k">define </span><span class="p">(</span><span class="nb">exp </span><span class="nv">x</span> <span class="nv">n</span><span class="p">)</span>
  <span class="p">(</span><span class="k">cond </span><span class="p">((</span><span class="nb">= </span><span class="nv">n</span> <span class="mi">0</span><span class="p">)</span> <span class="mi">1</span><span class="p">)</span>
        <span class="p">((</span><span class="nb">even? </span><span class="nv">n</span><span class="p">)</span> <span class="p">(</span><span class="nb">exp </span><span class="p">(</span><span class="nf">mul</span> <span class="nv">x</span> <span class="nv">x</span><span class="p">)</span> <span class="p">(</span><span class="nb">/ </span><span class="nv">n</span> <span class="mi">2</span><span class="p">)))</span>
        <span class="p">(</span><span class="k">else </span><span class="p">(</span><span class="nf">mul</span> <span class="nv">x</span> <span class="p">(</span><span class="nb">exp </span><span class="nv">x</span> <span class="p">(</span><span class="nb">- </span><span class="nv">n</span> <span class="mi">1</span><span class="p">))))))</span>
</pre></div>
<p>在不使用高阶函数或数据结构的情况下，定义矩阵乘法比较复杂，幸运的是，任何两个矩阵如果满足<span class="math">\(\begin{bmatrix}p+q&amp; q\\q&amp; p\end{bmatrix}\)</span>的形式，则其乘积也一定满足这种形式，于是可以用两个参数p和q来表示这种线性变换：</p>
<div class="math">
\begin{equation*}
a, b \rightarrow aq + bq + bp, ap + bq
\end{equation*}
</div>
<p>以及连续两次线性变换对应的新参数：</p>
<div class="math">
\begin{equation*}
p, q \rightarrow p^2 + q^2, q^2 + 2pq
\end{equation*}
</div>
<p>最终得出Fibonacci数的算法（见SICP习题1.19）：</p>
<div class="highlight"><pre><span></span><span class="p">(</span><span class="k">define </span><span class="p">(</span><span class="nf">square</span> <span class="nv">x</span><span class="p">)</span> <span class="p">(</span><span class="nb">* </span><span class="nv">x</span> <span class="nv">x</span><span class="p">))</span>
<span class="p">(</span><span class="k">define </span><span class="p">(</span><span class="nf">fib-fast</span> <span class="nv">n</span><span class="p">)</span>
  <span class="p">(</span><span class="k">define </span><span class="p">(</span><span class="nf">fib-iter</span> <span class="nv">count</span> <span class="nv">p</span> <span class="nv">q</span> <span class="nv">b</span> <span class="nv">a</span><span class="p">)</span>
    <span class="p">(</span><span class="k">cond </span><span class="p">((</span><span class="nb">= </span><span class="nv">count</span> <span class="mi">0</span><span class="p">)</span> <span class="nv">b</span><span class="p">)</span>
          <span class="p">((</span><span class="nb">even? </span><span class="nv">count</span><span class="p">)</span> <span class="p">(</span><span class="nf">fib-iter</span> <span class="p">(</span><span class="nb">/ </span><span class="nv">count</span> <span class="mi">2</span><span class="p">)</span>
                                   <span class="p">(</span><span class="nb">+ </span><span class="p">(</span><span class="nf">square</span> <span class="nv">p</span><span class="p">)</span> <span class="p">(</span><span class="nf">square</span> <span class="nv">q</span><span class="p">))</span>
                                   <span class="p">(</span><span class="nb">+ </span><span class="p">(</span><span class="nf">square</span> <span class="nv">q</span><span class="p">)</span> <span class="p">(</span><span class="nb">* </span><span class="mi">2</span> <span class="nv">p</span> <span class="nv">q</span><span class="p">))</span>
                                   <span class="nv">b</span>
                                   <span class="nv">a</span><span class="p">))</span>
          <span class="p">(</span><span class="k">else </span><span class="p">(</span><span class="nf">fib-iter</span> <span class="p">(</span><span class="nb">- </span><span class="nv">count</span> <span class="mi">1</span><span class="p">)</span>
                          <span class="nv">p</span>
                          <span class="nv">q</span>
                          <span class="p">(</span><span class="nb">+ </span><span class="p">(</span><span class="nb">* </span><span class="nv">a</span> <span class="nv">q</span><span class="p">)</span> <span class="p">(</span><span class="nb">* </span><span class="nv">b</span> <span class="nv">q</span><span class="p">)</span> <span class="p">(</span><span class="nb">* </span><span class="nv">b</span> <span class="nv">p</span><span class="p">))</span>
                          <span class="p">(</span><span class="nb">+ </span><span class="p">(</span><span class="nb">* </span><span class="nv">a</span> <span class="nv">p</span><span class="p">)</span> <span class="p">(</span><span class="nb">* </span><span class="nv">b</span> <span class="nv">q</span><span class="p">))))))</span>
  <span class="p">(</span><span class="k">cond </span><span class="p">((</span><span class="nb">&lt; </span><span class="nv">n</span> <span class="mi">2</span><span class="p">)</span> <span class="nv">n</span><span class="p">)</span>
        <span class="p">(</span><span class="k">else </span><span class="p">(</span><span class="nf">fib-iter</span> <span class="p">(</span><span class="nb">- </span><span class="nv">n</span> <span class="mi">1</span><span class="p">)</span> <span class="mi">0</span> <span class="mi">1</span> <span class="mi">1</span> <span class="mi">0</span><span class="p">))))</span>
</pre></div>
<p>这个算法和前面的指数计算一样，时间复杂度为对数级。</p>
<p>（完）</p>
<script type='text/javascript'>if (!document.getElementById('mathjaxscript_pelican_#%@#$@#')) {
    var align = "center",
        indent = "0em",
        linebreak = "false";

    if (false) {
        align = (screen.width < 768) ? "left" : align;
        indent = (screen.width < 768) ? "0em" : indent;
        linebreak = (screen.width < 768) ? 'true' : linebreak;
    }

    var mathjaxscript = document.createElement('script');
    mathjaxscript.id = 'mathjaxscript_pelican_#%@#$@#';
    mathjaxscript.type = 'text/javascript';
    mathjaxscript.src = 'https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.3/latest.js?config=TeX-AMS-MML_HTMLorMML';

    var configscript = document.createElement('script');
    configscript.type = 'text/x-mathjax-config';
    configscript[(window.opera ? "innerHTML" : "text")] =
        "MathJax.Hub.Config({" +
        "    config: ['MMLorHTML.js']," +
        "    TeX: { extensions: ['AMSmath.js','AMSsymbols.js','noErrors.js','noUndefined.js'], equationNumbers: { autoNumber: 'none' } }," +
        "    jax: ['input/TeX','input/MathML','output/HTML-CSS']," +
        "    extensions: ['tex2jax.js','mml2jax.js','MathMenu.js','MathZoom.js']," +
        "    displayAlign: '"+ align +"'," +
        "    displayIndent: '"+ indent +"'," +
        "    showMathMenu: true," +
        "    messageStyle: 'normal'," +
        "    tex2jax: { " +
        "        inlineMath: [ ['\\\\(','\\\\)'] ], " +
        "        displayMath: [ ['$$','$$'] ]," +
        "        processEscapes: true," +
        "        preview: 'TeX'," +
        "    }, " +
        "    'HTML-CSS': { " +
        "        availableFonts: ['STIX', 'TeX']," +
        "        preferredFont: 'STIX'," +
        "        styles: { '.MathJax_Display, .MathJax .mo, .MathJax .mi, .MathJax .mn': {color: 'inherit ! important'} }," +
        "        linebreaks: { automatic: "+ linebreak +", width: '90% container' }," +
        "    }, " +
        "}); " +
        "if ('default' !== 'default') {" +
            "MathJax.Hub.Register.StartupHook('HTML-CSS Jax Ready',function () {" +
                "var VARIANT = MathJax.OutputJax['HTML-CSS'].FONTDATA.VARIANT;" +
                "VARIANT['normal'].fonts.unshift('MathJax_default');" +
                "VARIANT['bold'].fonts.unshift('MathJax_default-bold');" +
                "VARIANT['italic'].fonts.unshift('MathJax_default-italic');" +
                "VARIANT['-tex-mathit'].fonts.unshift('MathJax_default-italic');" +
            "});" +
            "MathJax.Hub.Register.StartupHook('SVG Jax Ready',function () {" +
                "var VARIANT = MathJax.OutputJax.SVG.FONTDATA.VARIANT;" +
                "VARIANT['normal'].fonts.unshift('MathJax_default');" +
                "VARIANT['bold'].fonts.unshift('MathJax_default-bold');" +
                "VARIANT['italic'].fonts.unshift('MathJax_default-italic');" +
                "VARIANT['-tex-mathit'].fonts.unshift('MathJax_default-italic');" +
            "});" +
        "}";

    (document.body || document.getElementsByTagName('head')[0]).appendChild(configscript);
    (document.body || document.getElementsByTagName('head')[0]).appendChild(mathjaxscript);
}
</script>
    </div>
<nav class="nav sidebar">
    <div class="siteinfo">
        <div class="sitename"><a href="../..">coinfaces</a></div>
        <div class="tagline">Another Side of Life</div>
    </div>

        <a href="../../categories/">categories</a>
        <a href="../..">&larr; Home</a>
</nav><footer class="footer">
    <span>
        &copy; jpli &middot;
        under <a rel="license" href="http://creativecommons.org/licenses/by-sa/4.0/">CC-BY-SA 4.0</a>
    </span>
    |
    <span>
        Powered by:
        <a href="http://blog.getpelican.com/">Pelican</a>
    </span>
</footer></body>
</html>